﻿namespace Leetcode.N0022;
public class Solution
{
    public IList<string> GenerateParenthesis(int n)
    {
        var letters = new char[n * 2];
        var ans = new List<string>();
        for (int i = 0; i < n; i++)
        {
            letters[i] = '(';
            letters[i + n] = ')';
        }

        this.GenerateParenthesis(letters, n - 1, n, ans);

        return ans;
    }

    private void GenerateParenthesis(char[] letters, int leftIndex, int rightCount, IList<string> list)
    {

        list.Add(new string(letters));

        for (int i = 1; i <= Math.Min(rightCount, leftIndex); i++)
        {
            letters[leftIndex] = ')';
            letters[leftIndex + i] = '(';
            this.GenerateParenthesis(letters, leftIndex - 1, i, list);
            letters[leftIndex] = '(';
            letters[leftIndex + i] = ')';
        }
    }
}